package com.markus.code.exam.pingduoduo;

import java.util.*;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/1 20:05
 * todo:
 */
public class Solution {
    public static class Element<V>{
        public V value;
        public Element(V v){
            value = v;
        }
    }
    public static class UnionAndSet<V>{
        public HashMap<V,Element<V>> elementMap;
        public HashMap<Element<V>,Element<V>> fatherMap;
        public HashMap<Element<V>,Integer> sizeMap;

        public UnionAndSet(List<V> list){
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for(V v: list){
                Element<V> element = new Element<V>(v);
                elementMap.put(v,element);
                fatherMap.put(element,element);
                sizeMap.put(element,1);
            }
        }
        public Element<V> getHeader(V v){
            Element<V> element = elementMap.get(v);
            Stack<Element> stack = new Stack<>();
            while(element != fatherMap.get(element)){
                Element father = fatherMap.get(element);
                stack.push(element);
                element = father;
            }
            while(!stack.isEmpty()){
                fatherMap.put(stack.pop(),element);
            }
            return element;
        }
        public void union(V v1,V v2){
            if(elementMap.containsKey(v1) && elementMap.containsKey(v2)){
                Element father_v1 = getHeader(v1);
                Element father_v2 = getHeader(v2);
                if(father_v1 != father_v2){
                    int v1_len = sizeMap.get(father_v1);
                    int v2_len = sizeMap.get(father_v2);
                    Element<V> big = v1_len>v2_len?father_v1:father_v2;
                    Element<V> small = big==father_v1?father_v2:father_v1;
                    fatherMap.put(small,big);
                    sizeMap.put(big,v1_len+v2_len);
                    sizeMap.remove(small);
                }
            }
        }
        public void takeDown(V v){
            Element<V> element = elementMap.get(v);
            Element<V> father = fatherMap.get(element);
            fatherMap.put(element, element);
            sizeMap.put(element,1);
            sizeMap.put(father,sizeMap.get(father)-1);
        }
    }
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length==0 || grid[0].length==0){
            return 0;
        }
        List<String> list = new ArrayList<>();
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[i].length;j++){
                if(grid[i][j]=='1'){
                    String position = String.valueOf(i)+"_"+String.valueOf(j);
                    list.add(position);
                }
            }
        }
        UnionAndSet<String> unionAndSet = new UnionAndSet<>(list);
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[i].length;j++){
                if(grid[i][j]!='1'){
                    continue;
                }
                String position = String.valueOf(i)+"_"+String.valueOf(j);
                if(j-1>=0 && grid[i][j-1]=='1'){
                    String up = String.valueOf(i)+"_"+String.valueOf(j-1);
                    unionAndSet.union(up,position);
                }
                if(i-1>=0 && grid[i-1][j]=='1'){
                    String left = String.valueOf(i-1)+"_"+String.valueOf(j);
                    unionAndSet.union(left,position);
                }
            }
        }
        int max = 0;
        for (Map.Entry<Element<String>, Integer> entry : unionAndSet.sizeMap.entrySet()) {
            Integer value = entry.getValue();
            max = Math.max(max,value);
        }

        return unionAndSet.sizeMap.size();
    }
    private List<String> distance(char [][]grid){
        List<String> pos = new ArrayList<>();
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[i].length;j++){
                if (grid[i][j] == '0'){
                    String position = i+"_"+j;
                    String up = null;
                    String left = null;
                    String bottom = null;
                    String right = null;
                    if (i-1>=0){
                        up = (i-1)+"_"+j;
                    }
                    if (j-1>=0){
                        left = i+"_"+(j-1);
                    }
                    if (i+1<grid.length){
                        bottom = i+1+"_"+j;
                    }
                    if (j+1<grid[i].length){
                        right = i+"_"+String.valueOf(j+1);
                    }

                    pos.add(position);
                }
            }
        }
        return pos;
    }
//    private int max(char[][] grid,UnionAndSet<String> unionAndSet){
//
//    }
}
